package com.sheng.leetcode.year2022.month10.day08;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/10/08
 *<p>
 * 870. 优势洗牌<p>
 *<p>
 * 给定两个大小相等的数组nums1和nums2，<p>
 * nums1相对于 nums的优势可以用满足nums1[i] > nums2[i]的索引 i的数目来描述。<p>
 * 返回 nums1的任意排列，使其相对于 nums2的优势最大化。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]<p>
 * 输出：[2,11,7,15]<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]<p>
 * 输出：[24,32,8,12]<p>
 *<p>
 * 提示：<p>
 * 1 <= nums1.length <= 105<p>
 * nums2.length == nums1.length<p>
 * 0 <= nums1[i], nums2[i] <= 109<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/advantage-shuffle">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0870 {

    @Test
    public void test01() {
//        int[] nums1 = {2,7,11,15}, nums2 = {1,10,4,11};
        int[] nums1 = {12,24,8,32}, nums2 = {13,25,32,11};
        System.out.println(Arrays.toString(new Solution().advantageCount(nums1, nums2)));
    }
}
// 超时
//class Solution {
//    public int[] advantageCount(int[] nums1, int[] nums2) {
//        // 思考：针对nums2中的i元素而言，从nums1中获取到比它大的元素中最小且没有用过的元素，放入对应位置i中即可
//        int length = nums1.length;
//        int[] ans = new int[length];
//        // 将nums1数组中的元素排序后放入集合中
//        List<Integer> collect = Arrays.stream(nums1).boxed().sorted(Comparator.comparingInt(o -> o)).collect(Collectors.toList());
//        for (int i = 0; i < length; i++) {
//            for (int j = 0; j < collect.size(); j++) {
//                // 集合中存在元素满足条件，
//                if (collect.get(j) > nums2[i]) {
//                    ans[i] = collect.remove(j);
//                    break;
//                }
//                if (j == collect.size() - 1) {
//                    // 代表没有nums1中没有找到符合条件的数，那么将nums1中还未使用的最小的数放入i位置
//                    ans[i] = collect.remove(0);
//                    break;
//                }
//            }
//        }
//        return ans;
//    }
//}

/**
 * 执行用时：57 ms, 在所有 Java 提交中击败了94.21%的用户
 * 内存消耗：55.7 MB, 在所有 Java 提交中击败了92.12%的用户
 */
class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        // nums2索引
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        Arrays.sort(nums1);
        //根据nums2数据升序，排序nums2(索引)
        Arrays.sort(idx, (i, j) -> nums2[i] - nums2[j]);
        // nums2(索引)的左右指针
        int L = 0, R = n - 1;
        // 遍历nums1
        for (int i : nums1) {
            // 可以满足 nums1[i] > nums2[i]
            if (i > nums2[idx[L]]) {
                nums2[idx[L++]] = i;
            } else {
                //丢到数组最后
                nums2[idx[R--]] = i;
            }
        }
        return nums2;
    }
}
